package org.concepts.algorithm.sort;

import org.concepts.algorithm.utils.MathUtils;

/**
 * Selection sort is an in place sorting algorithm that scans the array and the
 * puts the lowest number in the first position. It then starts from the next
 * position (nth where n-1 is sorted) and finds the lowest in the array and puts
 * it in the nth position. This continues till the whole array is sorted.
 * 
 * @author vvvv
 * 
 * @param <E>
 */
public class SelectionSort<E extends Number> implements Sorter<E> {

  private boolean useRecursion = false;

  public boolean isUseRecursion() {
    return useRecursion;
  }

  /**
   * Set to true if you want this algorithm to use recursion. By default it will
   * traverse the array in the same method. Recursion method is just to show
   * that we could write the algorithm either way.
   * 
   * @param useRecursion
   */
  public void setUseRecursion(boolean useRecursion) {
    this.useRecursion = useRecursion;
  }

  @Override
  public E[] sort(E[] input) {

    if (input == null) {
      return input;
    }

    if (useRecursion) {
      int startN = 0;
      return selectionSort(startN, input);
    } else {
      return selectionSort(input);
    }
  }

  /**
   * Implements selection sort by array traversal (don't need recursion). [DAA
   * pg 98]
   * 
   * @param input
   * @return
   */
  private E[] selectionSort(E[] input) {
    for (int inputCnt = 0; inputCnt < input.length - 1; inputCnt++) {

      int minCnt = inputCnt;

      for (int findMinCnt = inputCnt; findMinCnt < input.length; findMinCnt++) {
        if (MathUtils.compare(input[findMinCnt], input[minCnt]) < 0) {
          minCnt = findMinCnt;
        }
      }

      MathUtils.swap(input, inputCnt, minCnt);

    }
    return input;
  }

  /**
   * This is a O(n^2) algorithm where our basic unit of operation is comparison.
   * Starting from the first element, we do the comparison of each element of
   * the array with the other elements of the array that are present after it.
   * Recursion is used to implement this algorithm. We exit when we reach the
   * end of the array.
   * 
   * @param startN
   * @param input
   * @return
   */
  private E[] selectionSort(int startN, E[] input) {
    if ((startN + 1) >= input.length) {
      return input;
    }

    E min = null;
    int minN = 0;

    for (int currN = startN; currN < input.length; currN++) {
      if (min == null || MathUtils.compare(input[currN], min) < 0) {
        min = input[currN];
        minN = currN;
      }
    }

    input[minN] = input[startN];
    input[startN] = min;

    return selectionSort(startN + 1, input);
  }

}
